package com.leetcode.algorithm.y22.m08.w4;

/**
 * 76. 最小覆盖子串
 * 
 * https://leetcode.cn/problems/minimum-window-substring/
 * 
 * @author jie.deng
 *
 */
class Question0076Solution01 {

	public String minWindow(String s, String t) {
		int[] cntArr = new int['z' - 'A' + 1];
		for (int i = 0; i < t.length(); i++) {
			cntArr[t.charAt(i) - 'A']++;
		}
		int diffCnt = 0;
		for (int i = 0; i < cntArr.length; i++) {
			if (cntArr[i] > 0) {
				diffCnt++;
			}
		}

		int min = s.length() + 1;
		String ans = "";
		int[] cntArrT = new int['z' - 'A' + 1];
		int len = s.length();
		int left = 0;
		for (int right = 0; right < len; right++) {
			cntArrT[s.charAt(right) - 'A']++;
			if (cntArrT[s.charAt(right) - 'A'] == cntArr[s.charAt(right) - 'A']) {
				diffCnt--;
			}
			while (diffCnt == 0) {
				int winSize = right - left + 1;
				if (winSize < min) {
					min = winSize;
					ans = s.substring(left, right + 1);
				}
				cntArrT[s.charAt(left) - 'A']--;
				if (cntArrT[s.charAt(left) - 'A'] == cntArr[s.charAt(left) - 'A'] - 1) {
					diffCnt++;
				}
				left++;
			}
		}

		return ans;
	}

}